第10.11节 基于层次的聚类算法

各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。

本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！

• 10.11 基于层次的聚类算法
• 10.11.1 聚类思想
• 10.11.2 聚类原理
• 10.11.3 Single-Link原理
• 10.11.4 Single-Link实现
• 10.11.5 Single-Link示例
• 10.11.6 Complete-Link原理
• 10.11.7 Complete-Link实现
• 10.11.8 Complete-Link示例
• 10.11.9 Ward原理
• 10.11.10 Ward实现
• 10.11.11 Ward示例
• 10.11.12 小结
• 引用

10.11 基于层次的聚类算法

经过前面几节内容的介绍，我们已经清楚了-means、-means++、基于权重的-means和DBSCAN这4种聚类算法的原理与实现。总的来说这4种聚类算法各有千秋，分别都能在一些独特的场景中发挥自己的优势。在接下来的这篇文章中，笔者将会为大家介绍第5种常见的聚类算法，层次聚类算法（Hierarchical Clustering）。那为什么需要层次聚类算法呢？

现在想象这么一个场景，假如你有大量病人的就医资料，需要通过聚类将其划分为不同的科室，例如消化科、呼吸科和皮肤科等等。但是除此之外，你还想顺便得到每个科室下具体病症的情况，例如呼吸科下面可能有肺炎病人、普通感冒病人等等。如果是通过前面介绍的4种聚类算法来进行建模，那么显然只能得到以科室为颗粒度的聚类结果[1]。

不过此时有读者可能会说，直接以病症为颗粒度进行聚类不就解决了吗？虽然理论上可以这么做，但是这种做法的弊端在于K值太大聚类结果可能不会太理想。同时，在其它我们不知道样本的层次结构中（假如在上面例子中不知道肺炎和感冒属于呼吸科），还能够通过层次聚类算法来发现这种潜在的结构。

10.11.1 聚类思想

在数据挖掘和统计分析中，层次聚类也叫做层次聚类分析（Hierarchical Cluster Analysis, HCA），旨在得到样本簇结构的同时发现样本分布的层次结构[2]。同时，层次聚类算法一般来说可以分为两种，一种是自下而上（bottom-up）的凝聚层次聚类（Agglomerative Clustering）和自上而下的分裂层次聚类（Divisive Clustering）。

凝聚层次聚类算法在聚类伊始会将数据中的每个样本点均看作是一个独立的簇结构，然后迭代将当前状态下最相似的两个簇进行合并，直到最后只剩下一个簇时聚类结束。对于分裂层次聚类算法来说则恰恰相反，分裂层次聚类算法在聚类伊始将所有的样本点都看成是一个簇，然后迭代将当前状态下最大的簇划分为两部分，直到最后将整个数据集划分成个簇结束[2]。

由于在实际应用中基于自上而下的分裂层次聚类使用较少，所以笔者后续将只介绍采用不同策略的的凝聚层次聚类算法。

10.11.2 聚类原理

在知道了层次聚类算法的基本思想后，我们再来看聚类过程的具体步骤。根据上面的介绍，我们可以将整个聚类过程归结为如下3步：

（1）将每个样本点均初始化为一个单独的簇；

（2）如果当前只存在一个簇则进入第（3）步，否则寻找当前状态下最相似的两个簇进行合并；

（3）返回整个聚类合并结果[1]。

如图10-25所示从到一共有10个样本点，下面笔者将按照上述3个步骤来对凝聚层次聚类算法的聚类过程进行示例。

图 10-25. 层次聚类算法原理图

如图10-25右侧所示，首先将这10个样本点均看作是一个单独的簇结构；其次假定此时在所有簇的两两组合中，和这两个簇最相似，那么则将其合并为一个簇；由于此时不止一个簇所以继续迭代，将和这两个簇进行合并得到簇；进一步，根据同样的方式将会得到簇；同理，再次将与合并得到簇；将和合并得到簇；将和合并得到簇；将和合并得到；将与合并得到簇；最后，将和合并得到簇。由于此时只剩下一个簇，所以层次聚类过程结束。与此同时，我们还可以通过图10-25左侧所示的树状图（Dendrogram）来观察每个簇内部层次结构。

介绍到这里肯定有朋友会问，既然凝聚层次聚类算法的终止条件是只剩下一个簇，那么聚类结束后的簇结构到是怎么样的呢？如图10-25左侧所示，在整个聚类过程中，如果不进行最后1次合并那么将会得到两个簇结构；如果在倒数第2次停止合并那么将会得到3个簇结构，以此类推。同时，在每个簇的内部还能看到剩余样本的层次结构。因此实际情况中，如果我们知道真实的簇数量K，那么完全可以在只剩下K个簇的时候停止合并，后续的代码实现也将遵循这一准则。

经过上面的介绍我们发现，凝聚层次聚类算法有两个关键的要素：距离的计算方式和相似性的度量方式（Linkage Criteria）。这一点就类似于K近邻算法一样，也需要两个关键的要素（距离度量方式和决策规则）。因为采用不同的距离计算方式，在后续进行相似性计算时将会得到不同的划分结果。通常在凝聚层次聚类中，距离的度量方式有欧式距离、平方欧氏距离和曼哈顿距离等等。对于相似性度量方式来说，在凝聚层次聚类算法中常用的有Single-Link、Complete-Link、Ward和UPGMA等等[2]。在接下来的内容，笔者将以前面3种相似性计算方式为例来进行介绍。

10.11.3  Single-Link原理

使用Single-Link作为相似性衡量标准的凝聚层次聚类算法也被称之为最近邻聚类（Nearest Neighbour Clustering），其核心思想是根据两个簇之间相邻最近两个样本点的距离来作为相似性评判标准，距离越近则表示这两个簇约相似，即这两个簇越有可能被合并。

如图10-26所示，在聚类过程中对于任意两个簇结构来说，我们需要计算得到相邻两个簇最近样本点之间的距离作为这两个簇相似性的度量值；然后在所有结果中选择相似度最大的值（距离最小）对应的两个簇进行合并；最后按照同样的方法继续进行迭代直到剩余簇数量为1或到达指定值时结束[1]。

图 10-26. Single-Link原理图

假如现在某数据集一共有到这6个样本点，则聚类伊始将这6个样本点均视为6个不同的簇[3]。同时，任意两个簇之间的距离如图10-27所示。

图 10-27. 簇与簇之间的两两距离D1如图10-27所示，为一个距离矩阵，用来记录所有簇两两之间的距离。从图中可以看出，此时簇与簇之间的距离最短为17，即最相似，因此将这两个簇进行合并。在合并结束后两个簇便合并成了一簇，因此需要删除矩阵中簇和簇所在的行与列。同时，由于其它簇两两之间的距离并没有发生改变因此只需要更新簇与其它3个簇之间的最近距离即可，如下：更新后的距离矩阵如图10-28所示。图 10-28. 簇与簇之间的两两距离D2如图10-28所示，此时簇与簇和簇之间的距离均为21，因此需要将这3个簇进行合并。此时尤其需要注意的一点是，由于中是其中一个簇分别与另外两个簇的距离相等（且该距离是簇与簇之间的最短距离），因此可以同时将这3个簇合并到一起。假如此时是簇与的距离为17，簇和簇之间的距离也是17，那么本次只能是将与进行合并，或者是将与进行合并，而不能简单地直接将这4个簇进行合并。在簇与和进行合并后，只需要更新中簇与剩余其它簇之间的最近距离即可，如下：更新后的距离矩阵如图10-29所示。图 10-29. 簇与簇之间的两两距离D3如图10-29所示，此时只剩下和这两个簇，因此最后将这两个簇进行合并。最终，根据上述合并过程，我们可以得到如图10-30所示的树状图。图 10-30. Single-Link层次聚类树状图到此，对于基于Single-Link的凝聚层次聚类算法的原理就介绍完了，下面笔者再来介绍如何一步一步实现整个算法。

10.11.4 Single-Link实现

在正式介绍Single-Link实现之前，我们需要先定义节点类来保存每次合并后的簇结构信息，代码实现如下：

1 class ClusterNode(object):
2     def __init__(self, idx=None, centroid=None):
3         samples = []
4         if idx is not None:
5             samples = [idx]
6         self.samples = samples
7         self.n_samples = len(self.samples)  
8         self.children = {}  
9         self.centroid = centroid

在上述代码中，第6行用来保存当前簇结构中所有样本在原始数据集中的索引；第7行用来保存当前节点对应的样本数量；第8行是存当前节点对应的孩子节点，如果仅仅只是为了完成聚类任务那么这个参数也可以不用；第9行用来保存当前簇结构对应的簇中心，这个参数只用于Ward算法中。

进一步，定义一个类方法来完成簇与簇之间的合并过程，实现代码如下：

1     def merge(self, node):
2         self.samples += node.samples
3         self.children[id(node)] = node
4         self.n_samples = len(self.samples)

在定义完簇节点的相关信息后，下面便可以通过一个函数来实现Single-Link算法的逻辑功能，实现代码如下所示：

 1 def single_linkage(X, n_clusters, metric="euclidean"):
 2     cluster_nodes = [ClusterNode(i) for i in range(len(X))]  
 3     old_d = pairwise_distances(X, metric=metric)  
 4     n_merge = 0
 5     while len(cluster_nodes) > n_clusters:
 6         n_merge += 1
 7         merge_dims = None
 8         all_locations = np.where(np.abs(old_d - np.sort(old_d.ravel())[len(old_d)]) < 1e-6)
 9         for (row, col) in zip(*all_locations):
10             if row == col:
11                 continue
12             merge_dims = [row, col] 
13             break
14         merge_node = ClusterNode()
15                 del_nodes = [cluster_nodes.pop(dim) for dim in sorted(merge_dims, reverse=True)]
16         for node in del_nodes:
17             merge_node.merge(node)
18         cluster_nodes.insert(0, merge_node) 
19         new_d = deepcopy(old_d)
20         new_d = np.delete(np.delete(new_d, merge_dims, axis=0), merge_dims, axis=1)
21         new_d = np.pad(new_d, [1, 0])
22         old_d_dims = [i for i in range(len(old_d)) if i not in merge_dims]  
23         new_d_dims = [i for i in range(1, len(new_d))]
24         for i, j in zip(new_d_dims, old_d_dims):
25             value = np.inf
26             for k in merge_dims:
27                 value = np.min([old_d[k][j], value])  # 寻找最小距离
28             new_d[0][i] = new_d[i][0] = value  # 更新 new_d
29         old_d = new_d
30     return cluster_nodes

在上述代码中，第1行X表示数据集形状为[n_samples, n_features]，n_clusters表示簇的数量，metric表示样本间距离的计算方式，常见的有'cosine', 'euclidean', 'l1', 'l2','manhattan'等；第2行是初始化每个样本为一个簇节点；第3行用于计算簇与簇之间的距离距离，是一个形状为 [n_samples,n_samples]的对称矩阵，old_d[i][j]表示第i个簇到第j个簇之间的距离。第5行开始递归合并满足条件的簇结构；第7行用来记录需要合并的维度。

为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！